package puzzle.projecteuler.p100;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.net.URL;
import java.net.URLDecoder;
import java.util.ArrayList;
import java.util.List;


public class Problem018 {

	public static void main(String[] args) throws IOException {

		Integer[] ds = readData();
		
		//start
		int max = (int)Math.ceil((Math.sqrt(8.0*ds.length-7)-1)/2.0)-1;
		int[] lens = new int[ds.length];
		lens[0] = ds[0];
		
		for (int r = 1; r <= max; r ++) {
			for (int i = 0; i <= r; i ++) {
				int index = index(r, i);
				if (i == 0) {
					lens[index] = lens[index(r-1, 0)] + ds[index];
				} else if (i == r) {
					lens[index] = lens[index(r-1, i-1)] + ds[index];
				} else {
					lens[index] = Math.max(lens[index(r-1, i)], lens[index(r-1, i-1)]) + ds[index];
				}
			}
		}
		
		//get max of last row
		int index = index(max, 0);
		int r = 0;
		for (int i = 0; i <= max; i ++) {
			if (lens[index+i] > r) {
				r = lens[index+i];
			}
		}
		System.out.println(r);
	}
	
	public static int index(int r, int i) {
		return r*(r+1)/2+i;
	}

	public static Integer[] readData() throws IOException {

		URL url = Problem018.class.getResource("Problem018.txt");
		File file = new File(URLDecoder.decode(url.getPath(), "UTF-8"));
		List<Integer> ds = new ArrayList<Integer>(); 
		BufferedReader br = new BufferedReader(new FileReader(file));
		String line = null;
		while ((line = br.readLine()) != null) {
			String[] nums = line.split("\\s+");
			for (String num: nums) {
				ds.add(Integer.valueOf(num));
			}
		}
		br.close();
		return ds.toArray(new Integer[ds.size()]);
	}
}
